1. Field of the Invention
The present invention relates to a design of search-line in the computer network domain and, more particularly, to a stored don't-care based hierarchical search-line scheme making use of a content-addressable memory (CAM) to apply to IP addressing lookup.
2. Description of Related art
Content-addressable memory (CAM) is a memory that implements the lookup-table function in a single clock cycle using dedicated comparison circuitry. CAM is a high performance search engine. It compares input search data with its entire contents within a single clock cycle. A CAM cell serves two basic functions—bit storage and bit comparison. For bit storage, CAM plays as an ordinary memory. Different from the SRAM, CAM has a special mode—searching operation. High search speed is the most advantage of CAM. As CAM applications grow, the power problem deteriorates more than the area. How to make a trade-off between power, speed, and area is the most important issue of recent researches in large capacity CAMs.
CAM can be classified into binary CAM and ternary CAM. The binary CAM cell, has two states: “one” state and “zero” state. Different from binary CAM cell, the ternary CAM has an extra state, don't-care, which is suitable to be used in network applications. Because ternary CAM cell has this extra state, it needs an additional storage memory to store data.
FIG. 1 shows a simplified block diagram of a ternary CAM. A conventional Ternary CAM architecture is usually composed of memory cell array 32, address decoders 30, bit-lines pre-charge circuits 38, word match schemes 34, read sense amplifiers 42, address priority encoders 36 and data line 40. Generally, ternary CAM has three operation modes: write, read, and search. The input in FIG. 1 is called search word that is broadcasted onto the search-lines. The number of bits in a ternary CAM word is usually large, with existing implementations ranging from 36 to 144 bits. A typical ternary CAM employs a table size ranging between a few hundred entries to 32K entries, corresponding to an address space ranging from 7 bits to 15 bits. Each stored word has a match-line that indicates whether the search word and stored word are identical (the match case) or are different (a mismatch case, or miss). The match-lines are fed to an encoder that generates a binary match location corresponding to the match-line that is in the match state. An encoder is used in systems where only a single match is expected. In ternary CAM applications where more than one word may match, a priority encoder is used instead of a simple encoder. An address priority encoder 36 selects the highest priority matching location to map to the match result, with words in lower address locations receiving higher priority. The overall function of a ternary CAM is to take a search word and return the matching memory location.
The hierarchical search-line scheme divides the search-lines into a two-level hierarchy of global search-lines (GSLs) and local search-lines (LSLs). FIG. 2 shows a simplified hierarchical search-line scheme, where the match-lines are pipelined into two segments, and the search-lines are divided into four LSLs per GSL. As shown in FIG. 2, hierarchical search-lines are built on top of pipelined match-lines. The basic idea of hierarchical search-lines is to exploit the fact that few match-lines survive the first segment of the pipelined match-lines. In the figure, each LSL feeds only a single match-line (for simplicity), but the number of match-lines per LSL can be 64 to 256. The GSLs are active every cycle, but the LSLs are active only when necessary. Activating LSLs is necessary only when at least one of the match-lines fed by the LSL is active. In many cases, an LSL will have no active match-lines in a given cycle, hence there is no need to activate the LSL, saving power.
However, the search speed is also restricted by hierarchical search-line (HSL) scheme. The primary reason is that the control signal comes from the comparison result at the previous stage in the same block, causing search time delay because each stage has to await the previous stage to finish operations and await the logic gate delay on one stage of HSL to start the comparison. Besides, in order to get the control signal of the next stage, the buffer of the HSL needs to have a very large control logic gate, in which the area and power overhead caused by the pipeline flip-flops and the clock driver diminishes the usefulness of the approach.
Accordingly, the present invention aims to propose a stored don't-care based hierarchical search-line scheme to solve the above drawbacks in the prior art.